package solution10;

/**
 * 1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
 * 2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
 * 3, If p.charAt(j) == '*':
 *      here are two sub conditions:
 *      1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
 *      2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
 *           dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a
 *           or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
 *           or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty
 */
public class Solution {
    // 动态规划
    public boolean isMatch(String s, String p) {

        if (s == null || p == null) {
            return false;
        }
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true; // 初始状态为true
        for (int i = 0; i < p.length(); i++) {  //i从0开始，是因为输入p，第一个字符不为*
            if (p.charAt(i) == '*' && dp[0][i-1]) { // 递归初始化 (a*)隔2个后,递归初始化为true
                dp[0][i+1] = true;
            }
        }

        // 得到其他状态
        for (int i = 0 ; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                if (p.charAt(j) == '.') {   // isMatch(s.substring(1),p.substring(1))
                    dp[i+1][j+1] = dp[i][j];
                }
                if (p.charAt(j) == s.charAt(i)) { // isMatch(s.substring(1),p.substring(1))
                    dp[i+1][j+1] = dp[i][j];
                }
                if (p.charAt(j) == '*') {
                    if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                        dp[i+1][j+1] = dp[i+1][j-1]; // 隔2个
                    } else {
                        dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]); //  a* 匹配1个a \\  匹配多个a \\ 匹配0个a
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }

    //递归 慢
    public static boolean isMatch2(String s, String p) {
        if (p.length() == 0)
            return s.length() == 0;

        // length == 1 is the case that is easy to forget.
        // as p is subtracted 2 each time, so if original
        // p is odd, then finally it will face the length 1
        if (p.length() == 1)
            return (s.length() == 1) && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');

        // next char is not '*': must match current character
        if (p.charAt(1) != '*') {
            if (s.length() == 0)
                return false;
            else
                return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')
                        && isMatch2(s.substring(1), p.substring(1));
        }else{
            // next char is *
            // 循环判断a* 是否匹配多个a ,如果a*没有匹配的，直接跳过循环
            while (s.length() > 0 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.')) {
                if (isMatch2(s, p.substring(2))) // 隔2个递归，如aaa a*a  递归 aaa a -> true| aaa a*ab 递归aaa ab -> false
                    return true;
                s = s.substring(1);// 匹配前面多个一样的，例如aaab a*b -> a* 匹配前面的aaa (true)
            }
            // a*没有匹配，隔2个递归 aab c*a*b
            return isMatch2(s, p.substring(2));
        }
    }
}
